Wireless Local Area Networks (WLANs)
Wireless local area networks (WLANs) generally operate at peak speeds from 1 to 54 Mbps and have a typical range of 100 meters. Single-cell Wireless LANs, as shown in FIG. 1A, are suitable for small single-floor offices or stores. A station in a wireless LAN can be a personal computer, a bar code scanner, or other mobile or stationary device that uses a wireless network interface card (NIC) to make the connection over the RF link to other stations in the network. The single-cell wireless LAN 100 of FIG. 1A provides connectivity within radio range between wireless stations 102, 104A, 104B, 106, and 108. Access point 108 allows connections via the backbone network 110 to wired network-based resources, such as servers. A single-cell wireless LAN can typically support several users and still keep network access delays at an acceptable level. Multiple-cell wireless LANs provide greater range than does a single-cell, by means of a set of access points and a wired network backbone to interconnect a plurality of single-cell LANs. Multiple-cell wireless LANs can cover larger multiple-floor buildings. A mobile appliance (e.g., laptop computer, SmartPhone, or data collector) with the appropriate integrated chip set or a wireless network interface card (NIC) can roam within the coverage area while maintaining a live connection to the backbone network 11.
Of the multitude of wireless LAN specifications and standards, IEEE 802.11 technology has emerged as a dominant force in the enterprise WLAN market over the past years. The WiFi group, commonly known as the Wireless Ethernet Compatibility Alliance (WECA) has led its development. Supporters include 3Com, Alantro Communications, Apple, Artem, Breezecom, Cabletron, Cisco (Aironet), Compaq, Dell, ELSA, Enterasys, Fujitsu, Intermec, Intel, Intersil, Lucent/Agere, MobileStar, Nokia, Samsung, ShareWave, Symbol, Telxon, WavePort and Zoom.
IEEE 802.11b is the newest 802.11 standard—finalized in September 1999—which is an 11 Mbps high rate DSSS (direct sequence spread spectrum) standard for wireless networks operating in the 2.4 GHz band. 802.11b high-rate products started shipping in late 1999 Task Group E, a MAC enhancements study group recently completed a feasibility study on integrating Quality of Service (QoS) and security into the standard.
Open Air was the first wireless LAN standard, pioneered by the Wireless Interoperability Forum (WLIF), with Proxim as its main proponent. It employs FHSS (frequency hopped spread spectrum) in the 2.4 GHz band. A recent FCC ruling allowed use of 5 MHz channels, up from its previous 1 MHz, in the 2.4 GHz frequency. With wideband frequency hopping (WBFH) data rates of 10 Mbps are possible.
HomeRF was designed specifically for the home networking market. As with Open Air, WBFH permits data transmission speeds to extend to 10 Mbps (up from 2 Mbps), which makes HomeRF more competitive with 802.11 technology. However, although HomeRF has significant backing from Proxim, Compaq, Motorola, and others.
Bluetooth is aimed at the market of low-power, short-range, wireless connections used for remote control, cordless voice telephone communications, and close-proximity synchronization communications for wireless PDAs/hand-held PCs and mobile phones. It has been confused on occasion as a pure-play WLAN standard, which it is not.
IEEE 802.11a is the 5 GHz extension to 802.11b, will provide speeds as high as 54 Mbps at a range less than half of 802.11b. It will prove attractive in high traffic-density service areas, where reduction of the 802.11b power (and hence range) to increase re-use is not adequate. With QoS enhancements similar to those pursued for 802.11b presently, it will appeal especially to users familiar with the 802.11 architecture.
HiperLAN/2 is the European (and global) counterpart to the “American” 802.11a standard first ratified in 1996 (as HiperLAN/1) by the European Telecommunications Standards Institute (ETSI). HiperLAN/2 has QoS features.
The unveiling of 802.11 g, the 22 Mbps extension to 802.11b, will give further life to the 2.4 GHz band in the near term, where 802.11b operates. Much like 10/100 Mbps Ethernet wired LANs, the new standard will provide backward compatibility to 802.11b networks.
Wireless LAN specifications and standards include the IEEE 802.11 Wireless LAN Standard and the HIPERLAN Type 1 and Type 2 Standards. The IEEE 802.11 Wireless LAN Standard is published in three parts as IEEE 802.11-1999; IEEE 802.11a-1999; and IEEE 802.11b-1999, which are available from the IEEE, Inc. web site http://grouper.ieee.org/groups/802/11. An overview of the HIPERLAN Type 1 principles of operation is provided in the publication HIPERLAN Type 1 Standard, ETSI ETS 300 652, WA2 December 1997. An overview of the HIPERLAN Type 2 principles of operation is provided in the Broadband Radio Access Networks (BRAN), HIPERLAN Type 2; System Overview, ETSI TR 101 683 VI.I.1 (2000-02) and a more detailed specification of its network architecture is described in HIPERLAN Type 2, Data Link Control (DLC) Layer; Part 4. Extension for Home Environment, ETSI TS 101 761-4 V1.2.1 (2000-12). A subset of wireless LANs is Wireless Personal Area Networks (PANs), of which the Bluetooth Standard is the best known. The Bluetooth Special Interest Group, Specification of the Bluetooth System, Version 1.1, Feb. 22, 2001, describes the principles of Bluetooth device operation and communication protocols.
Collision Avoidance Techniques
Four general collision avoidance approaches have emerged: [1] Carrier Sense Multiple Access (CSMA) [see F. Tobagi and L. Kleinrock, “Packet Switching in Radio Channels: Part I—Carrier Sense Multiple Access Models and their Throughput Delay Characteristics”, IEEE Transactions on Communications, Vol 23, No 12, Pages 1400–1416, 1975], [2] Multiple Access Collision Avoidance (MACA) [see P. Karn, “MACA—A New Channel Access Protocol for Wireless Ad-Hoc Networks”, Proceedings of the ARRL/CRRL Amateur Radio Ninth Computer Networking Conference, Pages 134–140, 1990], [3] their combination CSMA/CA, and [4] collision avoidance tree expansion.
CSMA allows access attempts after sensing the channel for activity. Still, simultaneous transmit attempts lead to collisions, thus rendering the protocol unstable at high traffic loads. The protocol also suffers from the hidden terminal problem.
The latter problem was resolved by the MACA protocol, which involves a three-way handshake [P. Karn, supra]. The origin node sends a request to send (RTS) notice of the impending transmission; a response is returned by the destination if the RTS notice is received successfully; and the origin node proceeds with the transmission. This protocol also reduces the average delay as collisions are detected upon transmission of merely a short message, the RTS. With the length of the packet included in the RTS and echoed in the clear to send (CTS) messages, hidden terminals can avoid colliding with the transmitted message. However, this prevents the back-to-back re-transmission in case of unsuccessfully transmitted packets. A five-way handshake MACA protocol provides notification to competing sources of the successful termination of the transmission. [See V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, “MACAW: A media access protocol for wireless LANs”, SIGCOMM '94, Pages 212–225, ACM, 1994.]
CSMA and MACA are combined in CSMA/CA, which is MACA with carrier sensing, to give better performance at high loads. A four-way handshake is employed in the basic contention-based access protocol used in the Distributed Coordination Function (DCF) of the IEEE 802.11 Standard for Wireless LANs. [See IEEE Standards Department, D3, “Wireless Medium Access Control and Physical Layer WG,” IEEE Draft Standard P802.11 Wireless LAN, January 1996.]
Collisions can be avoided by splitting the contending terminals before transmission is attempted. In the pseudo-Bayesian control method, each terminal determines whether it has permission to transmit using a random number generator and a permission probability “p” that depends on the estimated backlog. [See R. L. Rivest, “Network control by Bayesian Broadcast”, IEEE Trans. Inform. Theory, Vol IT 25, pp. 505–515, September 1979.]
To resolve collisions, subsequent transmission attempts are typically staggered randomly in time using the following two approaches: binary tree and binary exponential backoff.
Upon collision, the binary tree method requires the contending nodes to self-partition into two groups with specified probabilities. This process is repeated with each new collision. The order in which contending nodes transmit is determined either by serial or parallel resolution of the tree. [See J. L. Massey, “Collision-resolution algorithms and random-access communications”, in Multi-User Communication Systems, G. Longo (ed.), CISM Courses and Lectures No. 265, New York: Springer 1982, pp. 73–137.]
In the binary exponential backoff approach, a backoff counter tracks the number of idle time slots before a node with pending packets attempts to seize the channel. A contending node initializes its backoff counter by drawing a random value, given the backoff window size. Each time slot the channel is found idle, the backoff counter is decreased by 1 and transmission is attempted upon expiration of the backoff counter. The window size is doubled every time a collision occurs, and the backoff countdown starts again. [See A. Tanenbaum, Computer Networks, 3rd ed., Upper Saddle River, N.J., Prentice Hall, 1996.] The Distributed Coordination Function (DCF) of the IEEE 802.11 Standard for Wireless LANs employs a variant of this contention resolution scheme, a truncated binary exponential backoff, starting at a specified window and allowing up to a maximum backoff range below which transmission is attempted. [IEEE Standards Department, D3, supra] Different backoff counters may be maintained by a contending node for traffic to specific destinations. [Bharghavan, supra]
In the IEEE 802.11 Standard, the channel is shared by a centralized access protocol—the Point Coordination Function (PCF)—which provides contention-free transfer based on a polling scheme controlled by the access point (AP) of a basic service set (BSS). [IEEE Standards Department, D3, supra] The centralized access protocol gains control of the channel and maintains control for the entire contention-free period by waiting a shorter time between transmissions than the stations using the Distributed Coordination Function (DCF) access procedure.
IEEE 802.11 Wireless LAN Overview
The IEEE 802.11 Wireless LAN Standard defines at least two different physical (PHY) specifications and one common medium access control (MAC) specification. The IEEE 802.11(a) Standard is designed to operate in unlicensed portions of the radio spectrum, usually the 5 GHz Unlicensed-National Information Infrastructure (U-NII) band. It uses orthogonal frequency division multiplexing (OFDM) to deliver up to 54 Mbps data rates. The IEEE 802.11(b) Standard is designed for the 2.4 GHz ISM band and uses direct sequence spread spectrum (DSSS) to deliver up to 11 Mbps data rates.
802.11 Architecture Components
The IEEE 802.11 Wireless LAN Standard describes the following components. The station (STA) is any wireless device with conformant 802.11 interfaces to the wireless medium. A Basic Service Set (BSS) consists of two or more wireless nodes, or STAs, which have recognized each other and have established communications. In the most basic form, stations communicate directly with each other on a peer-to-peer level. When stations can communicate only among themselves, we say we have an Independent Basic Service Set (IBSS). This type of arrangement is commonly referred to as an ad hoc network. It is often formed on a temporary basis. BSSs can communicate with one another and with other networks. The distribution system (DS) integrates different BSS into a network; it may take any form, but it is typically a wired LAN. It provides address mapping. In most instances, the BSS contains an Access Point (AP). The AP is a station. The main function of an AP is to provide access to the distribution system. All communications between stations or between a station and a wired network client go through the AP. The AP is analogous to a base station used in cellular phone networks. AP's are not mobile, and form part of the wired network infrastructure. When an AP is present, stations do not communicate on a peer-to-peer basis. A multiple-cell wireless LAN using the IEEE 802.11 Wireless LAN Standard is an Extended Service Set (ESS) network. An ESS satisfies the needs of large coverage networks of arbitrary size and complexity. FIG. 1A illustrates the components of a WLAN.
Because of the way BSSs are set up in a plug-and-play manner, it is not uncommon for the coverage areas of two distinct BSSs to overlap.
802.11 MAC Functions
The purpose of the MAC protocol is to provide for the delivery of user data; fair access control; and privacy. Each wireless station and access point in an IEEE 802.11 wireless LAN implements the MAC layer service, which provides the capability for wireless stations to exchange MAC frames. The MAC frame transmits management, control, or data between wireless stations and access points. After a station forms the applicable MAC frame, the frame's bits are passed to the Physical Layer for transmission. The same MAC protocol serves all PHY specifications.
In the IEEE 802.11 Standard, the channel is shared through two access mechanisms: DCF and PCF. The distributed coordination function (DCF) is the basic media access control method for 802.11. It is mandatory for all stations. It is based on contention.
The point coordination function (PCF) is an optional extension to DCF. It is a contention-free centralized access protocol, especially useful for periodic time-sensitive services like cordless telephony. It is based on a polling scheme controlled by the access point (AP) of a basic service set. The centralized access protocol gains control of the channel and maintains control for the entire contention-free period by waiting a shorter time between transmissions than the stations using the DCF access procedure.
DCF Access Mechanism
The distributed coordination function (DCF) is the basic access method in 802.11 LANs. The PCF employs the DCF access mechanism to gain control of the channel. DCF uses Carrier Sense Multiple Access/Collision Avoidance (CSMA/CA). This requires each station to listen for other users and if busy postpone transmission by a random delay, known as backoff.
The backoff procedure in DCF relies on the ability of every station to ‘hear’ all other stations. But this is not always the case. It is possible for a station unable to hear the source of a transmission to interfere with the receipt of that transmission. This is known as the ‘hidden node’ problem. The RTS/CTS exchange can be used to combat this problem. RTS/CTS is also a mechanism for reserving the channel for point-to-point transmissions; it involves the exchange of messages between the origin and destination.
The source of the transmission sends an RTS frame, which may, or may not, be heard by a hidden node. The RTS frame contains a ‘duration’ field that specifies the period of time for which the medium is reserved. The NAV of a STA is set by the duration field. The NAV is set by all stations detecting the RTS frame. Nodes other than the destination set the NAV at this value and refrain from accessing the medium until the NVA expires. Upon receipt of the RTS, the destination node responds with a CTS frame. It, too, contains a ‘duration’ field specifying the remaining period of time for which the medium is reserved. A station within interfering range from the destination, which may not hear the RTS, will detect the CTS and update its NAV accordingly. The NAV provides protection through the ACK. The NAV serves as a ‘virtual’ carrier sense mechanism. Thus, collision is avoided even though some stations are hidden from others.
The RTS/CTS procedure is invoked optionally. As a channel reservation mechanism, the RTS/CTS exchange is efficient only for longer frames because of the extra overhead involved.
In order to increase the probability of successful transfer across the medium, frames are fragmented into smaller ones. A MAC service data unit (MSDU) is partitioned into a sequence of smaller MAC protocol data units prior to transmission. DCF transmits MSDUs as independent entities, thus providing best-effort connectionless user data transport.
DCF Backoff Procedure
If the channel has been idle for a time period of length DIFS (defined below) when a new frame arrives, the station may transmit immediately. However, if it is busy, each station waits until transmission stops, and then enters into a random backoff procedure. Deferring transmission by a random delay tends to prevent multiple stations from seizing the medium immediately after a preceding transmission completes. A backoff delay is chosen randomly from a range of integers known as the contention window. This delay measures the total idle time for which a transmission is deferred. It is expressed in units of time slots.
The CSMA/CA protocol minimizes the chance of collisions between stations sharing the medium, by waiting a random backoff interval 128A or 128B of FIG. 1C, if the station's sensing mechanism indicates a busy medium when a frame arrives. The period of time immediately following completion of the transmission is when the highest probability of collisions occurs, as all stations with newly arrived frames will attempt to transmit. For example, stations 102, 104B, and 106 may be waiting for the medium to become idle while station 104A is transmitting, and stations 102, 104B, and 106 will attempt to transmit at the same time, once station 104A stops. Once the medium is idle, CSMA/CA protocol causes each station to delay its transmission by a random backoff time. For example, station 104B delays its transmission by a random backoff time 128B, which defers station 104B from transmitting its frame 124B, thereby minimizing the chance it will collide with those from other stations 102 and 106, which have also selected their backoff times randomly.
As shown in FIG. 1D, the CSMA/CA protocol computes the random backoff time 128B of station 104B as the product of a constant, the slot time, times a pseudo-random number RN which has a range of values from zero to a contention window CW. The value of the contention window for the first try to access the network by station 104B is CW1, which yields the first try random backoff time 128B.
Backoff Countdown
An internal timer is set to the selected backoff delay. The timer is reduced by 1 for every time slot the medium remains idle. Backoff countdown is interrupted when the medium becomes busy. The timer setting is retained at the current reduced value for subsequent countdown. Backoff countdown may start or resume following a busy channel period only if the channel has been idle for time interval of length equal to DIFS. If the timer reaches zero, the station may begin transmission. The backoff procedure is illustrated in FIG. 1.
When a collision occurs, retransmission is attempted using binary exponential backoff, which refers to the process of increasing the range from which another backoff delay is drawn randomly. The contention window size is doubled with every transmission retry. This serves as a good mechanism for adapting to congestion because collisions are a result of congestion; with congestion a wider window is desirable. In the example in FIG. 1D, if the first try to access the network by station 104B fails, then the CSMA/CA protocol computes a new CW by doubling the current value of CW as CW2=CW1 times 2. As shown in FIG. 1D, the value of the contention window for the second try to access the network by station 104B is CW2, which yields the second try random backoff time 128B′. Binary exponential backoff provides a means of adapting the window size to the traffic load. Stations are not forced to wait very long before transmitting their frame in low traffic load. On the first or second attempt, a station will make a successful transmission. However, if the traffic load is high, the CSMA/CA protocol delays stations for longer periods to avoid the chance of multiple stations transmitting at the same time. If the second try to access the network by station 104B fails, then the CSMA/CA protocol computes a new CW by doubling again the current value of CW as CW3=CW1 times 4. As shown in FIG. 1D, the value of the contention window for the third try to access the network by station 104B is CW3, which yields the third try random backoff time 128B″. The value of CW increases to relatively high values after successive retransmissions, under high traffic loads. This provides greater transmission spacing between stations waiting to transmit.
Inter-Frame Spaces
In addition to contending stations, the channel is accessed also by the PCF, and by other frames without contention. To prioritize transmissions or remove contention, special idle spaces are defined, the IFS (-Inter Frame Space), which are idle spaces required between frames. They are illustrated in FIG. 1B. Each interval defines the duration from the end of the last symbol of the previous frame 113 at time T1, to the beginning of the first symbol of the next frame. They are the following: The Short Interframe Space (SIFS) 115 allows some frames to access the medium without contention, such as an Acknowledgement (ACK) frame, a Clear to Send (CTS) frame, or a subsequent fragment burst of a previous data frame. These frames require expedited access to the channel. At any point in time there is a single frame needing transmission within this group, and if transmitted within a SIFS period, there will be no contention.
The PCF inter-frame space, PIFS, is next; it is used by the PCF to access the medium in order to establish a contention-free period. A contention-free period may be started before a DCF transmission can access the channel because PIFS is shorter than DIFS. The Priority Interframe Space 117 of FIG. 1B is used by the PCF to access the medium in order to establish contention-free period 116 starting at T2 and ending at T3. The point coordinator 105 in the access point 108 connected to backbone network 110 in FIG. 1A controls the priority-based Point Coordination Function (PCF) to dictate which stations in cell 100 can gain access to the medium. During the contention-free period 116, station 102 in FIG. 1A, for example, is directed by the access point 108 to transmit its data frame 122. The point coordinator 105 in the access point 108 sends a contention-free poll frame 120 to station 102, granting station 102 permission to transmit a single frame. All stations, such as stations 104A, 104B, and 106, in the cell 100 can only transmit during contention-free period 116 when the point coordinator grants them access to the medium. In this example, stations 104A and 104B, which have data sources 114A and 114B, must wait until the end of the contention-free period 116 at T3. This is signaled by the contention-free end frame 126 sent by the point coordinator in FIG. 1C. The contention-free end frame 126 is sent to identify the end of the contention-free period 116, which occurs when time expires or when the point coordinator has no further frames to transmit and no stations to poll.
DIFS (DCF inter-frame space) is the longest of the three. Transmissions other than ACKs must wait at least one DIFS before commencing. A contention-free session can be started by the PCF before a DCF transmission because DIFS is longer than PIFS. Upon expiration of a DIFS, the backoff timer begins to decrement. The distributed coordination function (DCF) Interframe Space 119 of FIG. 1B is used by stations 104A and 104B, for example, for transmitting data frames 124A and 124B, respectively, during the contention-based period 118. The DIFS spacing permits the PC of neighboring cells to access the channel before a DCF transmission by delaying the transmission of frames 124A and 124B to occur between T3 and T4 An Extended Interframe Space (EIFS) (not shown) goes beyond the time of a DIFS interval as a waiting period when a bad reception occurs. The EIFS interval provides enough time for the receiving station to send an acknowledgment (ACK) frame.
PCF Access Mechanism
The Point Coordination Function (PCF) is an optional extension to DCF. In a single BSS, PCF provides contention-free access to accommodate time bounded, connection-oriented services such as cordless telephony. PCF involves a point coordinator (PC), which operates at the access point of the BSS. It employs contention-free polling. The PC gains control of the medium at regular time intervals through the DCF CSMA/CA protocol using PIFS for access priority over DCF transmissions. The PC also distributes information relevant to the PCF within Beacon Management frames.
The transmissions coordinated under the PCF experience no contention because control of the channel is maintained through the use of IFS spaces shorter than or equal to PIFS. That is, all frame transmissions under the point coordination function may use an IFS that is smaller than DIFS, the IFS used for DCF transmissions. Point-coordinated traffic is also protected this way from contention with DCF transmissions in overlapping BSSs that operate on the same channel. The contention-free period is also protected by setting the network allocation vector (NAV) in stations.
The PC determines which station transmits when. First, the AP delivers broadcast data. Then, the PC polls STAs on the polling list to send their data. In order to use the channel efficiently, piggybacking of different types of frames, like data frames, ACKs and polls, is possible. For example, a PC data frame can be combined with a poll to a station. STA data frames can be combined with an ACK. A PC can combine an ACK to one station with data and a poll to another. One frame is transmitted per poll by a polled STA.
Stations are placed on the polling list when they associate or re-associate with a BSS, at their discretion. A station may opt not to be polled in order to save power.
Multi-BSS Environment
A BSS is an equivalent to a cell in a cellular system; the AP is equivalent to the base station. When multiple WLANs operate in the same physical space, they share the same wireless spectrum. Coordination of wireless spectrum use in multi-BSS systems is thus comparable to RF planning in a cellular system. But unlike in cellular systems, the RF planning problem in WLANs is made more difficult by the location of the APs. They are not placed on a regular hexagonal grid. When WLANs are installed in multi-tenant office buildings and multiple-unit dwellings, owners simply plug in their AP and start up their LAN. No attention is paid to who else is operating a WLAN nearby. The result is overlapping cell coverage.
Overlapping cells will offer new challenges with the proliferation of WLANs. If there are several PCs attempting to establish contention-free periods (CFPs), they must coordinate their access. Special mechanisms are thus needed to enable multiple PCs to coordinate use of the channel under PCF and provide CFPs for their respective BSS. The current standard does not provide adequate coordination for the operation of the PCF in cases where multiple BSSs are operating on the same channel, in overlapping physical space. New protocols are needed. A complete protocol suite for this purpose has not yet been presented. A BSS operates on a single channel, while several channels are available within each of the bands. There are 3 channels in the 2.4 GHz band and 8 in the 5 GHz band. Once a channel has been assigned, channel time can be shared by using a dynamic bandwidth allocation methods.
The similarity of multi-BSS systems with cellular systems can be exploited in channel assignment only when a single service provider manages all WLANs in a given physical space. Then regular re-use RF planning methods, apply. A re-use factor N=8 can be employed, see Benveniste U.S. Pat. No. 5,740,536. However, repeating assignment of the same channel by a tessellation cannot be used with WLANs whose locations are chosen in an ad hoc manner and may involve even co-located BSSs. Non-regular channel assignment would need to be deployed; it assigns channels optimally, while respecting the interference experienced between BSSs when assigned the same channel—see Benveniste U.S. Pat. No. 5,404,574.
Channel assignment must be adaptive. That is, they should be revised occasionally as the spatial distribution of powered stations changes over time; as different stations are powered on or off at different times, or users are entering and leaving the BSSs. A channel selected upon installation of a station may not be suitable at some future time. While channel selections must be revisited occasionally, dynamic (frame by frame) channel assignment is not feasible as the assigned channel provides control, in addition to data transport.
Self-configuration, which involves stations taking signal-strength measurements to determine during a system operation the interference relationships between BSSs can be employed for adaptive channel assignment—see Benveniste U.S. Pat. No. 6,112,092.
Quality of Service (QoS)
Quality of service (QoS) is a measure of service quality provided to a customer. The primary measures of QoS are message loss, message delay, and network availability. Voice and video applications have the most rigorous delay and loss requirements. Interactive data applications such as Web browsing have less restrained delay and loss requirements, but they are sensitive to errors. Non-real-time applications such as file transfer, Email, and data backup operate acceptably across a wide range of loss rates and delay. Some applications require a minimum amount of capacity to operate at all, for example, voice and video. Many network providers guarantee specific QoS and capacity levels through the use of Service-Level Agreements (SLAs). An SLA is a contract between an enterprise user and a network provider that specifies the capacity to be provided between points in the network that must be delivered with a specified QoS. If the network provider fails to meet the terms of the SLA, then the user may be entitled to a refund. The SLA is typically offered by network providers for private line, frame relay, ATM, or Internet networks employed by enterprises.
The transmission of time-sensitive and data application traffic over a packet network imposes requirements on the delay or delay jitter and the error rates realized; these parameters are referred to generically as the QoS (Quality of Service) parameters. Prioritized packet scheduling, preferential packet dropping, and bandwidth allocation are among the techniques available at the various nodes of the network, including access points, that enable packets from different applications to be treated differently, helping achieve the different quality of service objectives. Such techniques exist in centralized and distributed variations. The concern herein is with distributed mechanisms for multiple access in a variety of networks, such as cellular packet networks or wireless ad hoc networks. For example, when engaged in dynamic packet assignment in a cellular type of network, the base stations contend among themselves for a channel to be used within their respective cells. Although the channel may be used by the mobile station for an up-link transmission, the serving base station is the one contending. [Patent application Ser. No. 113006, M. Benveniste, “Asymmetric Measurement-Based Dynamic Packet Assignment system And Method For Wireless Data Services”, filed on Mar. 22, 2001,] In an ad hoc type of network, individual stations contend for the use of a channel.
Management of contention for the shared transmission medium must reflect the goals sought for the performance of the system overall. For instance, one such goal would be the maximization of goodput (the amount of good data transmitted as a fraction of the channel capacity) for the entire system, or of the utilization efficiency of the RF spectrum; another is the minimization of the worst-case delay. As multiple types of traffic with different performance requirements are combined into packet streams that compete for the same transmission medium, a multi-objective optimization is required.
QoS enhancements are necessary in order to facilitate streaming of voice and multimedia traffic together with data. The high error rates experienced in transmitting over a wireless medium can lead to delays and jitter that are unacceptable for such traffic. More delay is added by acknowledgements that become necessary for wireless transmissions, and by the RTS/CTS mechanism if used.
Ideally, one would want a multiple access protocol that is capable of effecting packet transmission scheduling as close to the optimal scheduling as possible but with distributed control. Distributed control implies both limited knowledge of the attributes of the competing packet sources and limited control mechanisms.
To apply any scheduling algorithm in random multiple access, a mechanism must exist that imposes an order in which packets will seize the medium. For distributed control, this ordering must be achieved independently, without any prompting or coordination from a control node. Only if there is a reasonable likelihood that packet transmissions will be ordered according to the scheduling algorithm can one expect that the algorithm's proclaimed objective will be attained.
What is needed is a distributed medium access protocol that schedules transmission of different types of traffic based on their service quality specifications. Depending on these specifications, one such scheduling algorithm would be to assign packets from applications with different service quality specifications different priorities. Higher priority packets would be given preference over lower priority ones in congestion conditions. But in general, it is not desirable to postpone transmission of lower priority packets merely because there are higher priority packets are queued for transmission. The latter would penalize the lower priority traffic classes excessively.